/*
 * @lc app=leetcode.cn id=92 lang=cpp
 *
 * [92] 反转链表 II
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* result = new ListNode();  // 新增链表伪头部
        result->next = head;

        ListNode* lleftNode = result;       // 需要反转的第一个节点的前一个节点
        ListNode* leftNode = result;        // 需要反转的第一个节点
        ListNode* rightNode = result;       // 需要反转的最后一个节点
        ListNode* rrightNode = result;      // 需要反转的最后一个节点的后一个节点
        
        // 寻找需要反转的节点
        for (int i = 0; i < left; i++) {
            lleftNode = leftNode;
            leftNode = leftNode->next;
        }
        for (int i = 0; i < right; i++) {
            rightNode = rightNode->next;
            rrightNode = rightNode->next;
        }

        // 反转链表
        ListNode* curNode = leftNode;       // 遍历过程中的当前节点
        ListNode* prevNode = rrightNode;    // 遍历过程中的前驱结点
        ListNode* nextNode = nullptr;       // 遍历过程中的后驱节点
        lleftNode->next = rightNode;

        while (curNode != rrightNode) {
            nextNode = curNode->next;
            curNode->next = prevNode;
            prevNode = curNode;
            curNode = nextNode;
        }
        
        return result->next;
    }
};
// @lc code=end

